package com.c2b.algorithm.newcoder.double_pointer;

/**
 * <a href="https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">接雨水问题</a>
 * <p>
 * 给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)
 * </p>
 * <p>
 * 数据范围：数组长度0≤n≤2×10^5，数组中每个值满足0<val≤10^9，保证返回结果满足0≤val≤10^9，
 * <p>
 * 要求：时间复杂度O(n)
 * </p>
 * <pre>
 *               __
 *              |  |
 *      __      |  |
 *     |  |   __|  |
 *     |  |__|  |  |
 *     |  |  |  |  |
 *     |  |  |  |  |
 *     |  |  |  |  |
 *       5  3  4  7    ==》3
 * </pre>
 *
 * @author c2b
 * @since 2023/3/15 16:36
 */
public class BM0094MaxWater_H {

    public long maxWater(int[] arr) {
        if (arr.length < 3) {
            return 0;
        }
        // 双指针：左指针从左往右，右指针从右往左
        int leftIndex = 0;
        int rightIndex = arr.length - 1;
        // 维护左侧最大值和右侧最大值
        int leftMax = arr[0];
        int rightMax = arr[arr.length - 1];
        int res = 0;
        while (leftIndex < rightIndex) {
            if (arr[leftIndex] <= arr[rightIndex]) {
                if (leftMax >= arr[leftIndex + 1]) {
                    // 从左往右，如果是递减的趋势，需要计算接雨水量，更新结果res
                    res = res + leftMax - arr[leftIndex + 1];
                } else {
                    // 如果是递增的趋势，需要更新最大值leftMax
                    leftMax = arr[leftIndex + 1];
                }
                leftIndex++;
            } else {
                // 从右往左，如果是递减的趋势，需要计算接雨水量，更新结果res
                if (rightMax >= arr[rightIndex - 1]) {
                    res = res + rightMax - arr[rightIndex - 1];
                } else {
                    // 如果是递增的趋势，需要更新最大值rightMax
                    rightMax = arr[rightIndex - 1];
                }
                rightIndex--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        BM0094MaxWater_H bm0094MaxWater_h = new BM0094MaxWater_H();
        System.out.println(bm0094MaxWater_h.maxWater(new int[]{5, 5, 1, 7, 1, 1, 5, 2, 7, 6}));
    }
}
